This invention relates to computer-generated composite documents and, more particularly, to mapping computer-generated composite documents as textures to three-dimensional models.
A displayed three-dimensional model is typically rendered by a processor according to predefined coordinates in a predefined three-dimensional space. In order to appear as a displayed solid three-dimensional model, a texture or textures are mapped to the surface of the three-dimensional model. One example of a texture is a repetitive pattern. Other examples of textures are markup documents that may be formatted to include one or more Joint Photographic Experts Group (JPEG), Graphics Interchange Format (GIF), Moving Pictures Experts Group (MPEG), two-dimensional animation, RealVideo, hypertext markup language (HTML) images.
Virtually all 3D rasterization engines (whether implemented in hardware of software) require that textures be a power of two in width and height. Further, some rasterization engines require that the texture be square. Even further, some rasterization engines have maximum size limitations, i.e., some engines cannot render textures that are larger than 1024 by 1024 pixels. If a client of the 3D rasterization engine, such as a three-dimensional modeling application, requires that a non-conforming source image be used as a texture, something has to be done. For example, if a three-dimensional modeling application requires a 200 by 300 pixel texture, the application is required to make some choices in order to meet the requirements or limitations of the rasterization engine. In the past, the three-dimensional modeling application""s choice was to either scale the texture down to 128 by 256 pixels (or 128 by 128 pixels) or scale the texture up to 256 by 512 pixels (or 512 by 512 pixels). Both techniques (scale up or scale down) have serious penalties (performance+image quality). Using a larger texture size has the obvious disadvantage of wasting memory. Also, if the application runs into a texture maximum size limit, in the past, the only choice was to scale down.
In some applications, scaling has other disadvantages. For example, if the texture image is to be mapped to an animated three-dimensional model using the MPEG format, each texture image in the animation sequence must be scaled. Since animation requires 30 or more frames per second, conventional rasterization engines would have a difficult if not impossible time performing the texture scaling required for displaying an animation sequence in real time.
Many hardware-implemented 3D rasterization engines require that the texture that is used be stored in video memory. Video memory is a very scarce resource. Video memory is much smaller than main memory and is used for many purposes other than textures, i.e., screen buffer, back buffer, and zbuffer. If a large texture is to be applied to a geometric surface defined by a mesh of polygons, such as triangles, there may not be enough room in video memory for the texture when the mesh is rendered. At present there are two ways to solve this problem. The first is to scale down the texture so that it fits into video memory. The second is to not use the hardware-implemented 3D rasterization engine and use a software engine instead. The first solution results in a low-quality image. Further, scaling down the texture may degrade performance. The second solution decreases performance speed when compared to hardware-implemented 3D rasterization.
Therefore, there exists a need for a new and improved method for efficiently mapping texture to the geometric surfaces of three-dimensional models. The present invention is directed to meeting this need.
In accordance with this invention, a method, system and computer-readable medium for tessellating textures and mapping the resulting texture fragments onto the geometric surfaces of a three-dimensional model are provided. First, the texture for a predetermined surface of the three-dimensional model is fragmented into texture fragments such that each fragment conforms to rasterization requirements. Next, the surface geometry of the associated surface of the three-dimensional model is fragmented based on the texture fragments. Then, each texture fragment is mapped to the corresponding surface geometry fragment. This process is repeated for each viewable surface of the three-dimensional model to be textured. After completion, the three-dimensional model with the texture images mapped to the geometric surfaces of the three-dimensional model is displayed.
In typical 3D rendering engines, the surface geometries of three-dimensional models are defined by meshes of polygons, the most typical polygon being a triangle. For a particular surface, e.g., the outside of a sphere, there may be many such triangles. In accordance with other aspects of this invention, each polygon, i.e., each triangle in the surface geometry is assigned to exactly one of the texture fragments; hence, the collection of triangles assigned to a particular texture fragment conforms to the associated geometry fragment.
In accordance with further aspects of this invention, a polygon, i.e., a triangle in the surface geometry that falls within two (or more) texture fragments, is subdivided into smaller polygons, i.e., triangles, sized such that each small triangle can be independently assigned to exactly one of the texture fragments. The texture coordinates for each vertex of a polygon (a triangle) are assigned to a particular texture fragment. The texture coordinates for each vertex are transformed based on the location of the texture fragments with respect to the original texture.
As will be readily appreciated from the foregoing summary, the invention provides a new and improved method, apparatus and computer-readable medium for tessellating textures and mapping the resulting texture fragments onto the geometric surfaces of a three-dimensional model. When employed in a 3D rendering system that is designed to render three-dimensional models whose geometric surfaces are defined by a mesh of polygons, the fragmentation algorithm of the invention results in a set of meshes each of which defines a geometric surface fragment that has a smaller texture than the original. By adjusting various parameters (i.e., the maximum width/height), it is possible to create geometric surface fragment meshes whose corresponding texture fragments are fairly small. Then, during rendering, each geometric surface fragment mesh can be rendered sequentially using a minimum of video memory for textures. Sequential rendering of geometric surface fragment meshes allows hardware-implemented 3D rasterization engines to be employed and, thus, the performance benefits of such engines to be obtained.